Power efficiency through tuple ranking in wireless sensor network monitoring.

In%2Dnetwork data acquisition and replication in mobile sensor networks.

Optimized query routing trees for wireless sensor networks.

Ninth ACM International Workshop on Data Engineering for Wireless and Mobile Access



Eleventh International Conference on Mobile Data Management

Future directions in sensor data management a panel discussion.

Parallel and Distributed Data Management.
Abstract. Knowledge discovery tools and techniques are used in an increasing number of scientific and commercial areas for the analysis of large data sets. When large data repositories are coupled with geographic distribution of data, users and systems, it is necessary to combine different technologies for implementing high-performance distributed knowledge discovery systems. On the other hand, computational grid is emerging as a very promising infrastructure for high-performance distributed computing. In this paper we introduce a software architecture for parallel and distributed knowledge discovery (PDKD) systems that is built on top of computational grid services that provide dependable, consistent, and pervasive access to high-end computational resources. The proposed architecture uses the grid services and defines a set of additional layers to implement the services of distributed knowledge discovery process on grid-connected sequential or parallel computers. 1


A multi%2Dobjective evolutionary algorithm for the deployment and power assignment problem in wireless sensor networks.

Eighth ACM International Workshop on Data Engineering for Wireless and Mobile Access

FSort external sorting on flash%2Dbased sensor devices.

KSpot Effectively Monitoring the K Most Important Events in a Wireless Sensor Network.
Abstract — This demo presents a graphical user interface and ranking system, coined KSpot, for effectively monitoring the K highest-ranked answers to a query Q in a Wireless Sensor Network. KSpot deploys state-of-the-art distributed Top-k query processing algorithms in order to realize both snapshot queries and historic queries minimizing the consumption of system resources and prolonging the lifetime of the deployed sensor network. Additionally, KSpot is user-friendly and customizable featuring an intuitive user interface that enables a user to express declarative SQL-like queries over any ad-hoc scenario and to display the results graphically as opposed to the traditional tabular representation. To demonstrate the applicability of our system during the conference, we will continuously identify the K conference rooms with the highest sound level and display them such that conference attendees will be able to quickly determine the rooms with the most active discussions. The demo will also allow attendees to customize the system by changing the target scenario (e.g., by adapting the K value, the sensed parameter, etc.). Finally, we will present KSpot’s system panel which continuously displays the savings in energy and messages that our system yields. I.
Perimeter%2DBased Data Replication in Mobile Sensor Networks.
Abstract—This paper assumes a set of n mobile sensors that move in the Euclidean plane as a swarm. Our objectives are to explore a given geographic region by detecting spatio-temporal events of interest and to store these events in the network until the user requests them. Such a setting finds applications in mobile environments where the user (i.e., the sink) is infrequently within communication range from the field deployment. Our framework, coined SenseSwarm, dynamically partitions the sensing devices into perimeter and core nodes. Data acquisition is scheduled at the perimeter, in order to minimize energy consumption, while storage and replication takes place at the core nodes which are physically and logically shielded to threats and obstacles. To efficiently identify the nodes laying on the perimeter of the swarm we devise the Perimeter Algorithm (PA), an efficient distributed algorithm with a low communication complexity. For storage and fault-tolerance we devise the Data Replication Algorithm (DRA), a voting-based replication scheme that enables the exact retrieval of events from the network in cases of failures. Our trace-driven experimentation shows that our framework can offer significant energy reductions while maintaining high data availability rates. In particular, we found that when failures are less than 60% failure then we can recover over 80 % of generated events exactly. I.
ETC Energy%2DDriven Tree Construction in Wireless Sensor Networks.

Mobile Sensor Network Data Management.

Finding the K highest%2Dranked answers in a distributed network.

Workload%2DAware Query Routing Trees in Wireless Sensor Networks.

Workload%2DAware Query Routing Trees in Wireless Sensor Networks.

Distributed Top%2DK Query Processing in Wireless Sensor Networks.

Identifying Failures in Grids through Monitoring and Ranking.

Top%2Dk Retrieval Techniques in Distributed Sensor Systems.

Metadata Ranking and Pruning for Failure Detection in Grids.
The objective of Grid computing is to make processing power as accessible and easy to use as electricity and water. The last decade has seen an unprecedented growth in Grid infrastructures which nowadays enables large-scale deployment of applications in the scientific computation domain. One of the main challenges in realizing the full potential of Grids is making these systems dependable. In this paper we present FailRank, a novel framework for integrating and ranking information sources that characterize failures in a grid system. After the failing sites have been ranked, these can be eliminated from the job scheduling resource pool yielding in that way a more predictable, dependable and adaptive infrastructure. We also present the tools we developed towards evaluating the FailRank framework. In particular, we present the FailBase Repository which is a 38GB corpus of state information that characterizes the EGEE Grid for one month in 2007. Such a corpus paves the way for the community to systematically uncover new, previously unknown patterns and rules between the multitudes of parameters that can contribute to failures in a Grid environment. Additionally, we present an experimental evaluation study of the FailRank system over 30 days which shows that our framework identifies failures in 93 % of the cases and can achieve this by only fetching 65 % of the available information sources. We believe that our work constitutes another important step towards realizing adaptive Grid computing systems.
Intensive Care Window A Multi%2DModal Monitoring Tool for Intensive Care Research and Practice.

SenseSwarm a perimeter%2Dbased data acquisition framework for mobile sensor networks.

MINT Views Materialized In%2DNetwork Top%2Dk Views in Sensor Networks.
Abstract—In this paper we introduce MINT (Materialized In-Network Top-k) Views, a novel framework for optimizing the execution of continuous monitoring queries in sensor networks. A typical materialized view V maintains the complete results of a query Q in order to minimize the cost of future query executions. In a sensor network context, maintaining consistency between V and the underlying and distributed base relation R is very expensive in terms of communication. Thus, our approach focuses on a subset V ′ ( ⊆ V) that unveils only the k highest-ranked answers at the sink for some user defined parameter k. We additionally provide an elaborate description of energy-conscious algorithms for constructing, pruning and maintaining such recursivelydefined in-network views. Our trace-driven experimentation with real datasets show that MINT offers significant energy reductions compared to other predominant data acquisition models.
The MicroPulse Framework for Adaptive Waking Windows in Sensor Networks.
Abstract—In this paper we present MicroPulse, a novel framework for adapting the waking window of a sensing device S based on the data workload incurred by a query Q. Assuming a typical tree-based aggregation scenario, the waking window is defined as the time interval τ during which S enables its transceiver in order to collect the results from its children. Minimizing the length of τ enables S to conserve energy that can be used to prolong the longevity of the network and hence the quality of results. Our method is established on profiling recent data acquisition activity and on identifying the bottlenecks using an in-network execution of the Critical Path Method. We show through tracedriven experimentation with a real dataset that MicroPulse can reduce the energy cost of the waking window by three orders of magnitude.
pFusion A P2P Architecture for Internet%2DScale Content%2DBased Search and Retrieval.

Distributed middleware architectures for scalable media services.

Distributed spatio%2Dtemporal similarity search.
In this paper we introduce the distributed spatio-temporal similarity search problem: given a query trajectory Q, we want to find the trajectories that follow a motion similar to Q, when each of the target trajectories is segmented across a number of distributed nodes. We propose two novel algorithms, UB-K and UBLB-K, which combine local computations of lower and upper bounds on the matching between the distributed subsequences and Q. Such an operation generates the desired result without pulling together all the distributed subsequences over the fundamentally expensive communication medium. Our solutions find applications in a wide array of domains, such as cellular networks, wildlife monitoring and video surveillance. Our experimental evaluation using realistic data demonstrates that our framework is both e#cient and robust to a variety of conditions.
Efficient Online State Tracking Using Sensor Networks.
Sensor networks are being deployed for tracking events of interest in many environmental or monitoring applications. Because of their distributed nature of operation, a challenging issue is how to accurately identify the aggregate state of the phenomenon that is being observed. This work presents an online mechanism for efficiently determining the overall network status, employing distributed operations that minimize the communication costs. Experiments on real data, suggest that the proposed metholology can be a viable solution for real world systems. 1.
Structuring topologically aware overlay networks using domain names.

Efficient indexing data structures for flash%2Dbased sensor devices.
this article we present two external memory index structures for the e#cient retrieval of records stored on the local flash memory of a WSD. Our index structures, MicroHash and MicroGF (Micro Grid Files), exploit the asymmetric read/write and wear characteristics of flash memory in order to o#er high performance indexing and searching capabilities in the presence of a low energy budget, which is typical for the devices under discussion. Both structures organize data and index pages on the flash media using a sorted by timestamp file organization. A key idea behind these index structures is that expensive random access deletions are completely eliminated. MicroHash enables equality searches by value in constant time and equality searches by timestamp in logarithmic time at a small cost of storing the index pages on the flash media. Similarly, MicroGF enables spatial equality and proximity searches in constant time. We have implemented these index structures in nesC, the programming language of the TinyOS operating system. Our trace-driven experimentation with several real datasets reveals that our index structures o#er excellent search performance at a small cost of constructing and maintaining the index
The threshold join algorithm for top%2Dk queries in distributed sensor networks.
In this paper we present the Threshold Join Algorithm (TJA),  which is an e#cient TOP-k query processing algorithm for distributed sensor networks. The objective of a top-k query is to find the k highest ranked answers to a user defined similarity function. The evaluation of such a query in a sensor network environment is associated with the transfer of data over an extremely expensive communication medium. TJA uses a non-uniform threshold on the queried attribute in order to minimize the number of tuples that have to be transferred towards the querying node. Additionally, TJA resolves queries in the network rather than in a centralized fashion, which minimizes even more the consumption of bandwidth and delay. Our preliminary experimental results, using our trace driven simulator, show that TJA is both practical and e#cient.
MicroHash An Efficient Index Structure for Flash%2DBased Sensor Devices.
In this paper we propose the MicroHash index, which is an efficient external memory structure for Wireless Sensor Devices (WSDs). The most prevalent storage medium for WSDs is flash memory. Our index structure exploits the asymmetric read/write and wear characteristics of flash memory in order to offer high performance indexing and searching capabilities in the presence of a low energy budget which is typical for the devices under discussion. A key idea behind MicroHash is to eliminate expensive random access deletions. We have implemented MicroHash in nesC, the programming language of the TinyOS [7] operating system. Our trace-driven experimentation with several real datasets reveals that our index structure offers excellent search performance at a small cost of constructing and maintaining the index. 1
Data Acquisition in Sensor Networks with Large Memories.
Wireless Sensor Networks will soon become ubiquitous, making them essential tools for monitoring the activity and evolution of our surrounding environment. However such environments are expected to generate vast amounts of temporal data that needs to be processed in a power-effective manner. To this date sensor nodes feature small amounts of memory which mostly limits their capabilities to queries that only refer to the current point in time. In this paper we initiate a study on the deployment of large memories at sensor nodes. Such an approach gives birth to an array of new temporal and top-k queries which have been extensively studied by the database community. Our discussion is in the context of the RISE (RIverside SEnsor) hardware platform, in which sensor nodes feature external flash card memories that provide them several Megabytes of storage. 1.
Towards In%2DSitu Data Storage in Sensor Databases.

Exploiting locality for scalable information retrieval in peer%2Dto%2Dpeer networks.
An important problem in unstructured peer-to-peer (P2P) networks is the efficient content-based retrieval of documents shared by other peers. However, existing searching mechanisms are not scaling well because they are either based on the idea of flooding the network with queries or because they require some form of global knowledge. We propose the Intelligent Search Mechanism (ISM) which is an efficient, scalable yet simple mechanism for improving the information retrieval problem in P2P systems. Our mechanism is efficient since it is bounded by the number of neighbors and scalable because no global knowledge is required to be maintained. ISM consists of four components: A Profiling Structure which logs queryhit messages coming from neighbors, a Query Similarity function which calculates the similarity queries to a new query, RelevanceRank which is an online neighbor ranking function and a Search Mechanism which forwards queries to selected neighbors. We deploy and compare ISM with a number of other distributed search techniques over static and dynamic environments. Our experiments are performed with real data over Peerware, our middleware simulation infrastructure which is deployed on 75 workstations. Our results indicate that ISM outperforms its competitors and that in some cases it manages to achieve 100 % recall rate while using only half of the network resources required by its competitors. Further, its performance is also superior with respect to the total query response time and our algorithm exhibits a learning behavior as nodes acquire more knowledge. Finally ISM works well in dynamic network topologies and in environments with replicated data sources.
Towards Self%2DManaging QoS%2DEnabled Peer%2Dto%2DPeer Systems.

Exploiting locality for scalable information retrieval in peer%2Dto%2Dpeer networks.
An important problem in unstructured peer-to-peer (P2P) networks is the efficient content-based retrieval of documents shared by other peers. However, existing searching mechanisms are not scaling well because they are either based on the idea of flooding the network with queries or because they require some form of global knowledge. We propose the Intelligent Search Mechanism (ISM) which is an efficient, scalable yet simple mechanism for improving the information retrieval problem in P2P systems. Our mechanism is efficient since it is bounded by the number of neighbors and scalable because no global knowledge is required to be maintained. ISM consists of four components: A Profiling Structure which logs queryhit messages coming from neighbors, a Query Similarity function which calculates the similarity queries to a new query, RelevanceRank which is an online neighbor ranking function and a Search Mechanism which forwards queries to selected neighbors. We deploy and compare ISM with a number of other distributed search techniques over static and dynamic environments. Our experiments are performed with real data over Peerware, our middleware simulation infrastructure which is deployed on 75 workstations. Our results indicate that ISM outperforms its competitors and that in some cases it manages to achieve 100 % recall rate while using only half of the network resources required by its competitors. Further, its performance is also superior with respect to the total query response time and our algorithm exhibits a learning behavior as nodes acquire more knowledge. Finally ISM works well in dynamic network topologies and in environments with replicated data sources.
On Constructing Internet%2DScale P2P Information Retrieval Systems.
Abstract. We initiate a study on the effect of the network topology on the performance of Peer-to-Peer (P2P) information retrieval systems. The emerging P2P model has become a very powerful and attractive paradigm for developing Internet-scale systems for sharing resources, including files, or documents. We show that the performance of Information Retrieval algorithms can be significantly improved through the use of fully distributed topologically aware overlay network construction techniques. Our empirical results, using the Peerware middleware infrastructure, show that the approach we propose is both efficient and practical. 1
A distributed middleware infrastructure for personalized services.
In this paper we present an overview of eRACE, a modular and distributed intermediary infrastructure that collects information from heterogeneous Internet sources according to registered profiles or end-user requests. Collected information is stored for filtering, transformation, aggregation, and subsequent personalized or wide-area dissemination on the wireline or wireless Internet. We study the architecture and implementation of the main module of eRACE, an HTTP proxy named WebRACE. WebRACE consists of a high-performance, distributed and multithreaded Web crawler, a multithreaded filtering processor and an object cache. We discuss the implementation of WebRACE in Java, describe a number of performance optimizations, and present its performance assessment.
A local search mechanism for peer%2Dto%2Dpeer networks.
One important problem in peer-to-peer (P2P) networks is searching and retrieving the correct information. However, existing searching mechanisms in pure peer-to-peer networks are inefficient due to the decentralized nature of such networks. We propose two mechanisms for information retrieval in pure peer-to-peer networks. The first, the modified Breadth-First-Search (BFS) mechanism, is an extension of the current Gnuttela protocol, allows searching with keywords, and is designed to minimize the number of messages that are needed to search the network. The second, the Intelligent Search mechanism, uses the past behavior of the P2P network to further improve the scalability of the search procedure. In this algorithm, each peer autonomously decides which of its peers are most likely to answer a given query. The algorithm is entirely distributed, and therefore scales well with the size of the network. We implemented our mechanisms as middleware platforms. To show the advantages of our mechanisms we present experimental results using the middleware implementation.
Design and Implementation of a Distributed Crawler and Filtering Processor.
Web crawlers are the key component of services running on Internet and providing searching and indexing support for the entire Web, for corporate Intranets and large portal sites. More recently, crawlers have also been used as tools to conduct focused Web searches and to gather data about the characteristics of the WWW. In this paper, we study the employment of crawlers as a programmable, scalable, and distributed component in future Internet middleware infrastructures and proxy services. In particular, we present the architecture and implementation of, and experimentation with WebRACE, a high-performance, distributed Web crawler, filtering server and object cache. We address the challenge of designing and implementing modular, open, distributed, and scalable crawlers, using Java. We describe our design and implementation decisions, and various optimizations. We discuss the advantages and disadvantages of using Java to implement the WebRACE-crawler, and present an evaluation of its performance. WebRACE is designed in the context of eRACE, an extensible Retrieval Annotation Caching Engine, which collects, annotates and disseminates information from heterogeneous Internet sources and protocols, according to XML-encoded user profiles that determine the urgency and relevance of collected information.
